/*
 * Copyright (c) 2010 Mathew Hall, University of Sheffield.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided
 * with the distribution.
 *
 * Neither the name of the University of Sheffield nor the names of its
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */
package search.fitnessfunctions;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import primitives.cluster.ClusterHead;
import primitives.cluster.IClusterLevel;
import primitives.graph.Node;
import primitives.graph.Transition;

public class LevenshteinFitnessFunction extends TreeFitnessFunction {

	/**
	 * 
	 */
	private static final long serialVersionUID = -8359411578421086205L;

        public static int led(String s1, String s2){
            int[][] distances = new int[s1.length()+1][s2.length()+1];

            for(int i =0; i<= s1.length(); i++)
                distances[i][0] = i;

            for(int i =0; i<= s2.length(); i++)
                 distances[0][i] = i;

            char test = s2.charAt(s2.length() - 1);
            test = s1.charAt(s1.length() - 1);

            for(int j = 1;j<= s2.length();j++){

                for(int i =1; i<=s1.length();i++){
                    if(s1.charAt(i-1) == s2.charAt(j-1)){
                        distances[i][j] = distances[i-1][j-1];
                    }else{
                        distances[i][j] = Math.min(
                                Math.min(distances[i-1][j] + 1, distances[i][j-1] +1), distances[i-1][j-1] +1);
                    }

                }

            }
            return distances[s1.length()][s2.length()];
        }

	public double evaluate(ClusterHead tree) {
		double total = 0;
		HashMap<Node, IClusterLevel> cs = new HashMap<Node, IClusterLevel>();

		for (IClusterLevel t : tree.getChildren()) {
			for (Node n : t.getNodes()) {
				cs.put(n, t);
			}
		}

		for (IClusterLevel t : tree.getChildren())
			total += getClusterScore(t, cs);

		return 1/(total+Double.MIN_VALUE);
	}

        //XXX: this version only does distance between inter-cluster nodes.
        //implementation that does it on extra cluster nodes too coming to a theater near you soon.
	public static double getClusterScore(IClusterLevel cluster,
			HashMap<Node, IClusterLevel> cs) {

		// initialise this so we can lookup what cluster each node lives in

		double total = 0;
		for (Node nFrom : cluster.getNodes()) {

			for(Node nTo:cluster.getNodes()){
                            total += led(nFrom.getLabel(),nTo.getLabel());
                        }
		}

		return total;
	}

}
